FIG. 1 is a schematic block diagram of an exemplary data transmission system of the type to which the present disclosure may be applicable. The data transmission system is a broadcasting system such as, for example, Digital Video Broadcasting (DVB) in which a transmitter 1 encodes data to be transmitted to a great number of receivers 2. The specific number of receivers 2 is generally not known. The transmission may be a radio transmission, with or without intervention of a relay satellite 3. Each receiver 2 includes an antenna 22 communicating, for example, over wire connection 21, with a television set 24. On the side of transmitter 1, the broadcaster communicates by a transmission antenna 11 with satellite 3 to broadcast programs and more generally any type of data. More generally, the communication support may be of any type (Internet network, for example).
FIG. 1 is an example of a conventional one-way system where the receivers are not able to transmit information towards the satellite back to the transmitter. When the rights of access to certain programs are desired to be limited, it is necessary to add to television set 24, or to integrate thereto, a specific decoder 23 comprising keys enabling decoding of programs transmitted in ciphered manner.
Other conventional systems to which the present disclosure may apply are mobile telephony type systems in which, although a bi-directional communication channel exists between the operator and the mobile phone, the telephones are likely to receive broadcast data at a large scale, the operator being used as a relay only. Thus, it is difficult to consider having each receiver mobile phone communicate with the transmitter, the mobile phone behaving as a broadcast program receiver.
Most often, in conventional digital data transmission systems, the data flow is combined by an error-correction code (FEC, for forward error-correction), for enabling data recovery in case of interference in the transmission. The need for error-correction codes is also linked to the absence of a bi-directional communication preventing the receiver from indicating to the transmitter that it has not properly received part of the data.
Conventional systems typically use codes operating on a symmetrical binary channel (i.e., a bit can be received with no error or need for inversion). The error-correction code then checks the coherence of the bits received over the channel. Such error-correction codes are generally integrated to the physical layer.
There also exist conventional error-correction codes which operate on a symbol deletion channel, the symbols representing one or several bits or bytes. In symbol deletion channels, a symbol can either be received with no error, or destroyed by the channel. The symbol is the unit (byte or bit sequence) of processing by the system and its size is fixed. Such error-correction codes are generally used above the physical layer.
The present disclosure applies to the processing of error-correction codes at the level of the symbols, which most often have a size of several hundreds or several thousands of bytes or bits. Such error-correction coding generates an increase in the volume of data to be transmitted. A code rate is generally defined as being the number (k) of source symbols of the object to be transmitted (file, data flow, etc.) divided by a total number (n) of symbols. The n symbols are formed of the k source symbols and of the n−k parity symbols. Ratio k/n is smaller than or equal to one, and generally range between ⅔ and 1.
FIGS. 2A, 2B and 2C very schematically illustrate an exemplary error-correction coding of the type to which the present disclosure more specifically applies. It is a so-called LDPC (low density parity check) technique which exploits a parity matrix formed of a portion (or sub-matrix) of source symbols and of a portion (or sub-matrix) of parity symbols. The interpretation of such a matrix provides the transmitted parity symbols in addition to the source symbols.
FIG. 2A arbitrarily illustrates the flow 30 of source symbols S1, S2 . . . , Si, Si+1 . . . , Sk. FIG. 2B illustrates an example of a parity matrix 31 in which each of the first k columns (sub-matrix of source symbols) is assigned to one of symbols Si (i ranging between 1 and k) and each of the last n−k columns (sub-matrix of parity symbols) is assigned to one of parity symbols Pj (j ranging between 1 and n−k). The parity matrix comprises n−k lines L1, L2, etc. respectively assigned to the parity symbols to be calculated (and to be transmitted). Each element of the first matrix portion represents the taking into account (1) or not (0 or nothing) of the symbol of the corresponding column in the calculation of the symbol of the current line. The construction of the parity matrix is in this example said to be an LDPC staircase construction. It may be comprised of several thousands of columns and several thousands of lines.
To read matrix 31, it must be considered that the XOR-type combination (⊕) of the source or parity symbols identified in each line must be zero. For example, for the third line, S2⊕ . . . Si⊕ . . . ⊕P2⊕P3=0. On the receive side, knowing the parity matrix, it is possible to perform the operations of recovery of the transmitted source symbols.
The forming of the sub-matrix of source symbols depends on the application. For example, a pseudo-random generation may be used. A first solution to cipher a data flow would be to submit all the symbols upstream or downstream of the coding to a ciphering algorithm (AES, DES, RC4, etc.) . A disadvantage of such a solution is the processing time, be it on the transmit or receive side. Indeed, error-correction codes and ciphering algorithms have to process data integrally and are expensive in terms of access and/or memory consumption, as well as in terms of time of processing by a central processing unit, and thus of power.
Error-correction codes and ciphering algorithms, however, pursue other opposite goals. For example, an error-correction code aims at easing the data recovery, while a ciphering algorithm conversely aims at making the data recovery difficult for a receiver that does not have the right key. In addition, a data-ciphering function in error-correction codes generates a processing time which adds to the coding time. This problem is particularly acute on the receiver side, where processing capacities must be optimized.
FIG. 3 is a schematic block diagram illustrating a known method for ciphering data to be broadcast with an error-correction function. This method is described in article “Securing Bulk Content Almost for Free” by J. Byers et al., accepted in Computer Communication Journal in January 2005 (http://www.sciencedirect.com), to be published in “Computer Communication Journal, Special Issue on Network Security”.
On the side of transmitter 1, data DATA (block 12) to be transmitted are submitted to an FEC-type coding (block 13, CODE). The coding output provides a number of symbols greater than the number of input symbols. Then, 4% of the coded symbols (0.04(n−k)) are submitted to a ciphering (block 14, CIPHER) before transmission while the remaining 96% (0.96(n−k)) are transmitted directly. The coding may be of so-called Tornado type but it may also be, for example, of the LDPC type or of another suitable type. The transmitter of course includes transmission elements (not shown) for, for example, a radio broadcasting.
On the side of receiver 2, the flow of n−k symbols received from antenna 22 is, after demodulation and other receive processings (level matching, filtering, etc.), partly submitted (4%) to a deciphering (block 26, DECIPHER) before being entirely submitted to the decoding (block 25, DECODE), where 96% of the symbols need not be deciphered. The output of block 25 provides the flow of k decoded data symbols to be transmitted, for example to a television set 24. As a variation of the ciphering, a secure channel may also be used to transmit the 4% of the symbols intended to condition the proper obtaining of the data on the receiver side.
A disadvantage of the solution shown in FIG. 3 is that it is not secure enough (not resistant enough to crypto-analysis). Indeed, attacks on the 96% of the symbols not submitted to the ciphering may enable restoring the plain symbols. For example, by means of statistical analyses on the parity symbols which most often correspond to an XOR-type combination of source symbols, it is possible to recover the transmitted data. In particular, if the source data are formed of a significant number of null data (byte=00), the data are transmitted almost plainly. Further, in the case of a text file, a lexical analysis quite easily enables recovering portions of the original content. Moreover, if a same file is transmitted twice with a low number of difference bits, the obtained output flow is almost identical, which also is a weakness. For the ciphering to be efficient, the input flow would have to be perfectly random, which is in practice never the case.
Therefore what is needed is a system and method for improving the combination of error-correction code processing and a ciphering algorithm for use in digital data transmission.